package com.dh.leetcode.three;

import com.dh.leetcode.common.ListNode;
import org.junit.Test;

/**
 * @ClassName: _328_OddEvenLinkedList
 * @Description: 奇偶链表
 *
 * 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
 * <p>
 * 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/odd-even-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: shouzimu
 * @Date: 2020/11/13 15:06
 */
public class _328_OddEvenLinkedList {
    /**
     * 分拆成两个链表，然后将偶数的接到基数后面
     *
     * @param head
     * @return
     */
    public ListNode oddEvenList(ListNode head) {
        ListNode newHead = head;
        if (null != head && null != head.next) {
            ListNode even = head.next;
            ListNode evenTemp = even;
            while (null != even && null != even.next) {
                head.next = even.next;
                head = head.next;
                even.next = head.next;
                even = even.next;
            }
            head.next = evenTemp;
        }
        return newHead;
    }

    @Test
    public void oddEvenListTest() {
        ListNode node = ListNode.initNode(new int[]{1,2,3,4,5,6,7,8});
        node = oddEvenList(node);
        node.print();


        node = ListNode.initNode(new int[]{2, 1, 3, 5, 6, 4, 7});
        node = oddEvenList(node);
        node.print();

        node = ListNode.initNode(new int[]{1, 2, 3, 4, 5});
        node = oddEvenList(node);
        node.print();
    }
}
